﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using TSTree.fuctions;

/**
 * R*-tree class
 *
 * the header of the TRTree is organised as follows:
 * +-----------+-------------+---------------+---------------+--------------+------+
 * | dimension | noOfData | noOfDataNode | noOfInternalNode | rootIsData | root |
 * +-----------+-------------+---------------+---------------+--------------+------+
 *
 */

namespace TSTree
{
   public class TRTree
    {
        public int root;                     // block # of root node
        public TSNode rootPtr;              // root-node
        public Boolean rootIsData;         // true, if root is a data page
        public int dimension;                // dimension of the data's

        public int noOfData;	          // # of stored data
        public int noOfDataNode;	          // # of stored data pages
        public int noOfInternalNode;	          // # of stored directory pages

        public Boolean[] re_level;           // if re_level[i] is true,
        // there was a reinsert on level i
        public LinList re_data_cands = new LinList(); // data entries to reinsert -> see insert()

        public CachedBlockFile file;	      // storage manager for hard disk blocks

        int akt;                      // # of actually got data (get_next)
        byte[] header;
        float[] node_weight;          // weight for simulation of cache
        //protected int user_header;

        int getNoOfData()                 // returns # of stored data
        { return noOfData; }

        public int page_access = 0;

        /**
      * Construct a new R*-tree
      */
        public TRTree(String fname, int _b_length, int cache_size, int _dimension)
        {
            node_weight = new float[20];

            try
            {
                file = new CachedBlockFile(fname, _b_length, cache_size);
            }
            catch (Exception e)
            {
                Utilities.processError("TRTree creation: error in block file initialization", true);
            }

            // header allokieren und lesen
            header = new byte[file.getBlocklength()];

            // das ist zwar an sich hier Quatsch, aber damit wird die Variable
            // user_header richtig gesetzt, so dass beim Schreiben des Headers der
            // Aufrufer kein problem hat
            try
            {
                read_header(header);
            }
            catch (Exception e) { }

            dimension = _dimension;
            root = 0;
            rootPtr = null;
            rootIsData = true;
            noOfData = noOfInternalNode = noOfDataNode = 0;

            rootPtr = new TSDataNode(this);
            root = rootPtr.block;
        }
      
        /**
         * Construct(read) an R*-tree from disk
         */
        public TRTree(String fname, int cache_size)
        // bereits vorhandenen R-Baum laden
        {
            node_weight = new float[20];

            // file existiert schon --> Blockgroesse wird im Konstruktor ignoriert
            try
            {
                file = new CachedBlockFile(fname, 0, cache_size);
            }
            catch (Exception e)
            {
                Utilities.processError("TRTree reading: error in block file initialization", true);
            }

            // header allokieren und lesen
            header = new byte[file.getBlocklength()];
            try
            {
                file.readHeader(header);
            }
            catch (Exception e)
            {
                Utilities.processError("TRTree header reading: error in block file initialization", true);
            }

            try
            {
                read_header(header);
            }
            catch (Exception e) { }

            rootPtr = null;

            if (getNoOfData() == 0)
            // Baum war leer -> Datenknoten anlegen und d einfuegen
            {
                rootPtr = new TSDataNode(this);
                root = rootPtr.block;
                rootPtr.level = 0;
            }
            else
                load_root();
        }

        /*
        void printinfo(FILE *f)
        {
            fprintf(f,"\n internal: %d data-nodes : %d Datas: %d \n",
            noOfInternalNode, noOfDataNode, noOfData);
        }*/

        /**
         * read serialized information from buffer to TRTree variables
         */
        void read_header(byte[] buffer)
        {
            MemoryStream byteIn = new MemoryStream(buffer);
            BinaryReader inReader = new BinaryReader(byteIn);

            dimension = inReader.ReadInt32();
            noOfData = inReader.ReadInt32();
            noOfDataNode = inReader.ReadInt32();
            noOfInternalNode = inReader.ReadInt32();
            rootIsData = inReader.ReadBoolean();
            root = inReader.ReadInt32();

            //user_header = &buffer[i];

            inReader.Close();
            byteIn.Close();
        }

        /**
         * store TRTree information to buffer serially
         */
        void write_header(byte[] buffer)
        {
            MemoryStream byteOut = new MemoryStream(buffer);
            BinaryWriter outWriter = new BinaryWriter(byteOut);

            outWriter.Write(dimension);
            outWriter.Write(noOfData);
            outWriter.Write(noOfDataNode);
            outWriter.Write(noOfInternalNode);
            outWriter.Write(rootIsData);
            outWriter.Write(root);
            outWriter.Write(dimension);

            //user_header = &buffer[i];

            byte[] bytes = byteOut.ToArray();
            for (int i = 0; i < bytes.Length; ++i)
                buffer[i] = bytes[i];

            outWriter.Close();
            byteOut.Close();
        }

        /**
         * load root information from disk
         */
        void load_root()
        {
            if (rootPtr == null)
                // create root and read its info from the appropriate disk block (root)
                // See TSDataNode and TSDirNode constructor
                if (rootIsData)
                    rootPtr = new TSDataNode(this, root);
                else
                    rootPtr = new TSDirNode(this, root);
        }

        /**
         * Insert a new data entry into the tree. Insertion is propagated to the
         * root node. If the root overflows, it has to be split into 2 nodes and
         * a new root will be introduced, to hold the split nodes.
         */
        public void insert(TSData d)
        {
            int i, j;                              // counters
            TSNode[] sn = new TSNode[1];           // potential new node when SPLIT takes place
            TSDirNode nrootPtr;                    // new root when the root is SPLIT
            int nroot;                             // block # of nrootPtr
            TSDirEntry de;                         // temp Object used to consruct new
                                                   // root dir entries when SPLIT takes place
            int split_root = Constants.NONE;       // return of rootPtr.insert(d)
            TSData d_cand, dc;                     // temp duplicates of d
            float[] nmbr;                          // rootPtr MBR

            // load root into memory
            load_root();

            /*
             * no overflow occured until now. re_level array indicates if a re_insert
             * has been done at the specific level of the tree. Initially all entries
             * in this array should be set to false
             */
            re_level = new Boolean[rootPtr.level + 1];
            for (i = 0; i <= rootPtr.level; i++)
                re_level[i] = false;

            /*
             * insert d into re_data_cands as the first entry to insert
             * make a copy of d because it shouldnt be erased later
             */
            dc = (TSData)d.clone(); //duplicate the data into dc
            re_data_cands.insert(dc); //insert the datacopy into the
            //list of pending to be inserted data
            j = -1;
            while (re_data_cands.getNoOfElements() > 0)
            {
                // first try to insert data, then directory entries
                d_cand = (TSData)re_data_cands.getFirst();
                if (d_cand != null)
                {
                    // since erase deletes the according data element of the
                    // list, we should make a copy of the data before
                    // erasing it
                    dc = (TSData)d_cand.clone();
                    re_data_cands.erase();

                    // start recursive insert from root
                    split_root = ((INode)rootPtr).insert(dc, sn);
                }
                else
                    Utilities.processError("TRTree::insert: inconsistent list re_data_cands", true);

                if (split_root == Constants.SPLIT)
                /*
                 * insert has lead to split --> create new root having as sons
                 * old root and sn
                 */
                {
                    //initialize new root
                    nrootPtr = new TSDirNode(this);
                    nrootPtr.hasDataSon = rootIsData;
                    nrootPtr.level = (short)(rootPtr.level + 1);
                    nroot = nrootPtr.block;

                    // a new TSDirEntry is introduced having as son the old root
                    de = new TSDirEntry(dimension, rootIsData, this);
                    nmbr = ((INode)rootPtr).getMBR();
                    // store the mbr of the root to the TSDirEntry
                    for (i = 0; i < 2 * dimension; i++)
                        de.bounces[i] = nmbr[i];
                    //System.arraycopy(nmbr, 0, de.bounces, 0, 2 * dimension);
                    de.son = rootPtr.block;
                    de.sonPtr = rootPtr;
                    de.sonIsData = rootIsData;
                    de.noOfData = ((INode)rootPtr).getNoOfData();
                    // add de to the new root
                    nrootPtr.insertEntry(de);

                    // a new TSDirEntry is introduced having as son the brother(split) of the old root
                    de = new TSDirEntry(dimension, rootIsData, this);
                    nmbr = ((INode)sn[0]).getMBR();
                    for (i = 0; i < 2 * dimension; i++)
                        de.bounces[i] = nmbr[i];
                    // System.arraycopy(nmbr, 0, de.bounces, 0, 2*dimension);
                    de.son = sn[0].block;
                    de.sonPtr = sn[0];
                    de.sonIsData = rootIsData;
                    de.noOfData = ((INode)sn[0]).getNoOfData();
                    nrootPtr.insertEntry(de);
                    
                    // update separators
                    float[] tempsep = nrootPtr.getSep(nrootPtr.entries[0].bounces, nrootPtr.entries[1].bounces);
                    for (int iz = 0; iz < dimension * 2; iz+=2)
                    {
                        nrootPtr.entries[0].leftsep[iz / 2] = nrootPtr.entries[0].bounces[iz];
                        nrootPtr.entries[1].rightsep[iz / 2] = nrootPtr.entries[1].bounces[iz + 1];

                        nrootPtr.entries[0].rightsep[iz/2] = tempsep[iz/2];
                        nrootPtr.entries[1].leftsep[iz/2] = tempsep[iz/2];
                    }
                    
                        // replace the root of the tree with the new node
                    root = nroot;
                    rootPtr = nrootPtr;

                   
                    // the new root is a directory node
                    rootIsData = false;
                }
                // go to the next data object to be (re)inserted
                j++;
            }

            // increase number of data in the tree after insertion
            noOfData++;
        }

      


        /**
         * Return the ith data element in the tree.
         * --> Propagate to the root node.
         */
        public TSData get(int i)
        {
            TSData d;

            // load root into main memory
            load_root();

            // propagate to the root node
            d = ((INode)rootPtr).get(i);

            return d;
        }

        /**
         * Print the objects in the tree that intersect with the parameter mbr.
         * --> Propagate to the root node.
         */
        public  void region(float[] mbr)
        {
            // load root node into main memory
            load_root();

            ((INode)rootPtr).region(mbr);
        }

        /**
         * Print the objects in the tree that intersect with the parameter point.
         * --> Propagate to the root node.
         */
        public void pointQuery(float[] p)
        {
            // load root node into main memory
            load_root();

            ((INode)rootPtr).pointQuery(p);
        }


        /*
        #ifdef S3
        template <class Data>
        void TRTree<Data>::neighbours(LinList<Data> *sl,
                    float eps,
                    Result *rs,
                    norm_ptr norm)
        {
            // load root node into main memory
            load_root();
     
            rootPtr->neighbours(sl, eps, rs, norm);
        }
        #endif // S3
         */

        /**
         * Return to Nearest the object in the tree that is nearest
         * to parameter point. --> Propagate to the root node.
         */
        public void NearestNeighborQuery(TSPoint QueryPoint, TSPoint Nearest)
        {
            float/*[]*/ nearest_distance/* = new float[1]*/;

            // load root node into main memory
            load_root();

            nearest_distance/*[0]*/ = Constants.MAXREAL;

            ((INode)rootPtr).nearestNeighborSearch(QueryPoint, Nearest, nearest_distance);
        }

        /**
         * Return to res the objects in the tree that are nearest
         * to parameter point. --> Propagate to the root node.
         */
        public void NearestNeighborQuery(TSPoint QueryPoint, SortedLinList res)
        {
            float nearest_distance;

            // load root node into main memory
            load_root();

            nearest_distance = Constants.MAXREAL;

            ((INode)rootPtr).nearestNeighborSearch(QueryPoint, res, nearest_distance);
        }

        /**
         * Return to res the k objects in the tree that are nearest
         * to parameter point. --> Propagate to the root node.
         */
        public void k_NearestNeighborQuery(TSPoint QueryPoint, int k, SortedLinList NeighborList)
        {
            int i, l, n;
            float nearest_distance;
            TSData p;

            nearest_distance = Constants.MAXREAL;

            load_root();

            // NeighborListListe vorbereiten
            NeighborList.setSorting(true);

            for (i = 0; i < k; i++)
            {
                p = new TSData(dimension);
                for (l = 0; l < dimension; l++)
                    p.data[l] = Constants.MAXREAL;
                p.distance = Constants.MAXREAL;
                NeighborList.insert(p);
            }

            ((INode)rootPtr).nearestNeighborSearch(QueryPoint, NeighborList, nearest_distance);
        }

        /**
         * Return to res the objects in the tree that intersect with the parameter point.
         * --> Propagate to the root node.
         */
        public void pointQuery(TSPoint p, SortedLinList res)
        {
            page_access = 0;

            // load root node into main memory
            load_root();
            ((INode)rootPtr).pointQuery(p, res);
        }

        /**
         * Return to res the objects in the tree that intersect with the parameter circle.
         * --> Propagate to the root node.
         */
      public void rangeQuery(TSPoint center, float radius, SortedLinList res)
        {
            page_access = 0;

            load_root();
            /////////////////////////////////////////////////////
            //page_access++;
            //byte[] block = new byte[file.getBlocklength()];
            //file.readBlock(block, 0);
            //////////////////////////////////////////////////////

            ((INode)rootPtr).rangeQuery(center, radius, res);
        }

        /**
         * Return to res the objects in the tree that intersect with the parameter ring,
         * defined by the circles provided that radius1<radius2.
         * --> Propagate to the root node.
         */
        public void ringQuery(TSPoint center, float radius1, float radius2, SortedLinList res)
        {
            page_access = 0;

            load_root();
            ((INode)rootPtr).ringQuery(center, radius1, radius2, res);
        }

        /**
         * Return to res the objects in the tree that intersect with the parameter mbr.
         * --> Propagate to the root node.
         */
        public void rangeQuery(float[] mbr, SortedLinList res)
        {
            page_access = 0;

            load_root();
            ((INode)rootPtr).rangeQuery(mbr, res);
        }


        public void range_nnQuery(float[] mbr, SortedLinList res, TSPoint Nearest)
        {
            TSPoint center;
            float distance = Constants.MAXREAL;
            Boolean success = false;
            int i;

            center = new TSPoint(dimension);
            for (i = 0; i < dimension; i++)
                center.data[i] = (mbr[2 * i] + mbr[2 * i + 1]) / (float)2.0;

            load_root();

            ((INode)rootPtr).range_nnQuery(mbr, res, center, distance, Nearest, success);
        }


        void overlapping(float[] p, int[] nodes_t)
        {
            load_root();

            ((INode)rootPtr).overlapping(p, nodes_t);
        }


        /**
         * Return to nodes_a[] the # of nodes at each level of the tree.
         * --> Propagate to the root node.
         */
        void nodes(int[] nodes_a)
        {
            load_root();

            ((INode)rootPtr).nodes(nodes_a);
        }

        /*
        void TRTree<Data>::writeinfo(FILE *f)
        {
            load_root();
            rootPtr->writeinfo(f);
            fprintf(f,"\n");
        }*/

        /**
         * Store to node_weight[] how many of the directory pages starting from the root
         * level can be stored in a cache with the paremeter cache size. Each entry in
         * node_weight stores the fraction of nodes at the specific level that will not
         * fit in the cache. For instance, node_weight[rootPtr.level=10]=0,
         * node_weight[9]=0, node_weight[8]=0, node_weight[7]=0.4, node_weight[6]=1,...
         * means that only the entries of the upper 3 levels can fully fit in cache, and
         * also a portion of the nodes at the 7th level.
         */
        void set_node_weight(int cache_size)
        {
            int[] nodes_tab = new int[20]; // holds the # of nodes at each level 0..19
            int i, j, rest;
            Boolean c = false;

            // calculate number of nodes per level
            for (i = 0; i < 20; i++)
                nodes_tab[i] = 0;

            nodes(nodes_tab); // propagate to root

            rest = cache_size;
            if (cache_size > 0)
                c = true;

            for (i = rootPtr.level; i > 0; i--)
            {
                if (c)
                // cache is not fully filled
                {
                    if (rest - nodes_tab[i] > 0)
                    // there is enough cache for this level
                    {
                        rest -= nodes_tab[i];
                        node_weight[i] = (float)0.0;
                    }
                    else
                    {
                        // this is the last level to be cached and not all
                        // nodes of the level are in general in the cache
                        node_weight[i] = (float)1.0 - ((float)rest / (float)nodes_tab[i]);
                        rest = 0;
                        c = false;
                    }
                }
                else
                    // cache is full
                    node_weight[i] = (float)1.0;
            }

            // data nodes are not in cache
            node_weight[0] = (float)1.0;

            Console.WriteLine("cache configuration (" + cache_size + " blocks cache)");
            for (i = 0; i < 10; i++)
                Console.WriteLine("level " + i + ": " + node_weight[i] + " of " + nodes_tab[i]);
        }

        public void delete()
        {
            try
            {
                write_header(header);
                file.setHeader(header);
            }
            catch (Exception e)
            {
                Utilities.processError("TRTree.delete: error in writing header", true);
            }
            if (rootPtr != null)
            {
                ((INode)rootPtr).delete();
            }
            try
            {
                file.flush();
            }
            catch (Exception e)
            {
                Utilities.processError("TRTree.delete: error in flushing file", true);
            }

            Console.WriteLine("TRTree saved: noOfData=" + noOfData +
                    " noOfInternalNode=" + noOfInternalNode +
                    " noOfDataNode=" + noOfDataNode);
        }

        /*
        protected void finalize () throws Throwable
        {
            write_header(header);
            Console.WriteLine("TRTree saved: noOfData=" + noOfData +
                                           " noOfInternalNode=" + noOfInternalNode +
                                           " noOfDataNode=" + noOfDataNode);
     
        }*/

        // converts a rect_to_rect relation to an intermediateMBR_to_rect relation
        // see SIGMOD'95 paper for details
        //public static short toMBRtopo(short topology)
        //{
        //    short ret = topology;

        //    if (relationSet.getBit(topology, (byte)0) == 1) // disjoint
        //        ret |= (short)(relationSet.p2((byte)1) + relationSet.p2((byte)7) + relationSet.p2((byte)6) + relationSet.p2((byte)5));

        //    if (relationSet.getBit(topology, (byte)1) == 1) // meet
        //        ret |= (short)(relationSet.p2((byte)7) + relationSet.p2((byte)6) + relationSet.p2((byte)5));

        //    if (relationSet.getBit(topology, (byte)2) == 1) // equal
        //        ret |= (short)(relationSet.p2((byte)6) + relationSet.p2((byte)5));

        //    if (relationSet.getBit(topology, (byte)3) == 1) // inside
        //        ret |= (short)(relationSet.p2((byte)7) + relationSet.p2((byte)4) + relationSet.p2((byte)2) + relationSet.p2((byte)6) + relationSet.p2((byte)5));

        //    if (relationSet.getBit(topology, (byte)4) == 1) // covered_by
        //        ret |= (short)(relationSet.p2((byte)7) + relationSet.p2((byte)2) + relationSet.p2((byte)6) + relationSet.p2((byte)5));

        //    // skip contain

        //    if (relationSet.getBit(topology, (byte)6) == (byte)1) // covers
        //        ret |= relationSet.p2((byte)5);

        //    if (relationSet.getBit(topology, (byte)7) == (byte)1) // overlap
        //        ret |= (short)(relationSet.p2((byte)6) + relationSet.p2((byte)5));

        //    return ret;
        //}

        /*  void constraints_query(rectangle rect, double[] distance, short direction, short topology, SortedLinList res) {
              short MBRtopo = toMBRtopo(topology);
        
              page_access = 0;
        
              load_root();
              ((Node)rootPtr).constraints_query(rect, distance, direction, MBRtopo, topology, res);
          }*/


        public void Close()
        {
            if(file != null)
                file.Close();
        }

       // return height of tree
        public int getHeight()
        {
            return this.rootPtr.level + 1;
        }
       // return node, entries following level
        public int noOfNodeByLevel(int level, TSNode root)
        {
            int count = 0;
            if (root.level == level) return 1;
            else
            {
                if (!((INode)root).isDataNode())
                {
                    for (int i = 0; i < root.getNoEntries(); i++)
                    {
                        count += noOfNodeByLevel(level, ((TSDirNode)root).entries[i].getSon());
                    }
                }
            }

            return count;
        }

        public int noOfInternalNodes(TSNode root)
        {
            int count = 0;
            if (root.level != 0) return 1;
            else
            {
                if (!((INode)root).isDataNode())
                {
                    for (int i = 0; i < root.getNoEntries(); i++)
                    {
                        count += noOfInternalNodes(((TSDirNode)root).entries[i].getSon());
                    }
                }
            }

            return count;
        }

        public int noOfLeafNode(TSNode root)
        {
            int count = 0;
            if (root.level == 0) return 1;
            else
            {
                if (!((INode)root).isDataNode())
                {
                    for (int i = 0; i < root.getNoEntries(); i++)
                    {
                        count += noOfLeafNode(((TSDirNode)root).entries[i].getSon());
                    }
                }
            }

            return count;
        }
        // return node, entries following level
        public int noOfEntriesByLevel(int level, TSNode root)
        {
            int count = 0;
            if (root.level == level) return root.getNoEntries();
            else
            {
                if (!((INode)root).isDataNode())
                {
                    for (int i = 0; i < root.getNoEntries(); i++)
                    {
                        count += noOfEntriesByLevel(level, ((TSDirNode)root).entries[i].getSon());
                    }
                }
            }

            return count;
        }

        public int noOfInternalEntries(TSNode root)
        {
            int count = 0;
            if (root.level != 0) return root.getNoEntries();
            else
            {
                if (!((INode)root).isDataNode())
                {
                    for (int i = 0; i < root.getNoEntries(); i++)
                    {
                        count += noOfInternalEntries(((TSDirNode)root).entries[i].getSon());
                    }
                }
            }

            return count;
        }
        public int noOfLeafEntries(TSNode root)
        {
            int count = 0;
            if (root.level == 0) return root.getNoEntries();
            else
            {
                if (!((INode)root).isDataNode())
                {
                    for (int i = 0; i < root.getNoEntries(); i++)
                    {
                        count += noOfLeafEntries(((TSDirNode)root).entries[i].getSon());
                    }
                }
            }

            return count;
        }

       // get total Nodes
        public int totalNode()
        {
            int c = 0;
            for (int i = 0; i <= this.rootPtr.level; i ++ )
            {
                c += noOfNodeByLevel(i, this.rootPtr);
            }

            return c;
        }

       
        public int totalEntries()
        {
            int c = 0;
            for (int i = 0; i <= this.rootPtr.level; i++)
            {
                c += noOfEntriesByLevel(i, this.rootPtr);
            }

            return c;
        }
        public float avgEntriesPerNode()
        {
            return (float)totalEntries() / totalNode();
        }

        public float avgEntriesPerNodeBylevel(int level)
        {
            return (float)noOfEntriesByLevel(level, this.rootPtr) / noOfNodeByLevel(level,this.rootPtr);
        }

        public float avgEntriesPerLeafNode()
        {
            return (float)noOfLeafEntries(this.rootPtr) / noOfLeafNode(this.rootPtr);
        }

        public float avgEntriesPerInternalNode()
        {
            return (float)noOfInternalEntries(this.rootPtr) / noOfInternalNodes(this.rootPtr);
        }

        public float avgWideTree()
        {
            return (float)totalNode() / getHeight();
        }

        public int noOfNodeLevel(int level)
        {
            int i = 0;
            i = noOfNodeByLevel(level, this.rootPtr);
            return i;
        }
    }
}
